#ifndef AVL_H
#define AVL_H

//TODO change to standard code style

#include <iostream>

using namespace std;

enum  cmp_t {
   MIN_CMP = -1,   // less than
   EQ_CMP  = 0,    // equal to
   MAX_CMP = 1     // greater than
};


struct AvlKey
{
	int vertex_id;
	double f;
};

class Comparable {
private:
   AvlKey  my_key_;

public:
   Comparable(int vertex_id, double f){
	   my_key_.vertex_id = vertex_id;
	   my_key_.f = f;
   };

   //~Comparable(){ delete myKey; }

   cmp_t Compare(AvlKey  key) const {
	   return (key.f == my_key_.f) ? EQ_CMP : ((key.f < my_key_.f) ? MIN_CMP : MAX_CMP);
   }

   AvlKey Key() const { return  my_key_; }

};

enum  dir_t 
 { LEFT = 0, RIGHT = 1 };

class AvlNode {
public:

   enum  { MAX_SUBTREES = 2 };

   static  dir_t Opposite(dir_t dir){ 
     return dir_t(1 - int(dir));
   }

   AvlNode(Comparable  *item=NULL);
   virtual ~AvlNode(void);

   Comparable* Data() const { return  myData; }

   AvlKey Key() const { return  myData->Key(); }

   //-1 => left subtree is taller than right subtree
   // 0 => left and right subtree are equal in height
   // 1 => right subtree is taller than left subtree
   short Bal(void) const { return  myBal; }

   // Get the item of the left/right subtree of this
   // item (the result may be NULL if there is no such item).
   AvlNode* Subtree(dir_t dir) const { return  mySubtree[dir]; }

   // Look for the given key. Return the item's adress or NULL if not found
   static Comparable* Search(AvlKey key, AvlNode* root, cmp_t cmp=EQ_CMP);

   // Insert the given key, return NULL if it was inserted
   static Comparable* Insert(Comparable* item, AvlNode* & root);

   // Pick the node with the highest key value (this oparation has always a cost of t=log(n))
   // Called by AvlTree::PickNode member operation 
   static Comparable* PickNode(AvlNode* & root);

      // Delete the given key from the tree. Return the corresponding
      // node, or return NULL if it was not found.
   static Comparable* Delete(AvlKey key, AvlNode* & root, cmp_t cmp=EQ_CMP);

      // Return the height of this tree
   int Height() const;

      // Verify this tree is a valid AVL tree, return TRUE if it is,
      // return FALSE otherwise
   int Check() const;


private:
   Comparable* myData; 
   AvlNode* mySubtree[MAX_SUBTREES];   // Pointers to subtrees
   short myBal;   // Balance factor

   void Reset(void) {
      myBal = 0 ;
      mySubtree[LEFT] = mySubtree[RIGHT] = NULL ;
   }

   static Comparable* Insert(Comparable* item,AvlNode* &root,int &change);

   static Comparable* Delete(AvlKey key, AvlNode* &root,int &change, cmp_t cmp=EQ_CMP);

   static Comparable* GetFirstData(AvlNode* &root,  cmp_t cmp=EQ_CMP);

   static int RotateOnce(AvlNode* &root, dir_t dir);

   static int RotateTwice(AvlNode* &root, dir_t dir);

   static int ReBalance(AvlNode* &root);

   cmp_t Compare(AvlKey key, cmp_t cmp=EQ_CMP) const;

private:
   AvlNode(const AvlNode &);
   AvlNode & operator=(const AvlNode &);

};

class AvlTree {
private:
   AvlTree(const AvlTree &);
   AvlTree & operator=(const AvlTree &);

   AvlNode* myRoot;  

public:
   AvlTree() : myRoot(NULL) {};
   ~AvlTree() { if (myRoot)  delete myRoot; }

   int IsEmpty() const {
      return  (myRoot == NULL);
   }

   // at worst case, cost O(log(n))
   Comparable* Search(AvlKey key, cmp_t cmp=EQ_CMP) {
	   return  AvlNode::Search(key, myRoot, cmp);
   }
   
   // at worst case, cost O(log(n))
   Comparable* Insert(Comparable* item) {
      return  AvlNode::Insert(item, myRoot);
   }
   
   // always has cost O(log(n))
   Comparable* PickNode(){
	   return AvlNode::PickNode(myRoot);
   }

   // at worst case, cost O(log(n))
   Comparable* Delete(AvlKey key, cmp_t cmp=EQ_CMP) {
      return  AvlNode::Delete(key, myRoot, cmp);
   }

   int Check() const {
      return  (myRoot) ? myRoot->Check() : 1;
   }
};


#endif
